package com.codingxyz.simple.linkList;

import java.io.Serializable;
import java.util.NoSuchElementException;

/**
 * 双向链表
 * 
 * @author sdc
 *
 * @param <E>
 */
public class LinkedList1<E> implements Serializable {

	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;

	/**
	 * 定义节点啊
	 * 
	 * @author sdc
	 *
	 * @param <E>
	 */
	private static class Node<E> {

		E item;

		// 指向下一个节点
		Node<E> next;

		// 指向前一个节点
		Node<E> prev;

		Node(Node<E> prev, E item, Node<E> next) {
			this.prev = prev;
			this.item = item;
			this.next = next;
		}

	}

	/**
	 * 第一个节点引用
	 */
	transient Node<E> first;

	/**
	 * 最后一个节点引用
	 */
	transient Node<E> last;

	/**
	 * list中元素数量
	 */
	transient int size = 0;

	/**
	 * 修改次数
	 */
	transient int modCount = 0;

	public LinkedList1() {

	}

	/**
	 * 把传入的元素变为第一个
	 * 
	 * @param e
	 */
      	private void linkFirst(E e) {
		Node<E> f = first;
		Node<E> newNode = new Node<E>(null, e, f);

		if (f == null) {// 说名是空节点，第一次加入空节点
			last = newNode;
		} else {
			f.prev = newNode;
		}

		first = newNode;
		size++;
		modCount++;
	}

	/**
	 * 在最后面加入一个元素
	 * 
	 * @param e
	 */
	private void linkLast(E e) {
		Node<E> l = last;
		Node<E> newNode = new Node<>(l, e, null);

		if (l == null) {
			first = newNode;
		} else {
			l.next = newNode;
		}

		last = newNode;
		size++;
		modCount++;
	}

	/**
	 * 在指定节点前插入信息
	 * 
	 * @param e
	 * @param succ
	 *            指定节点信息
	 */
	private void linkBefore(E e, Node<E> succ) {
		// 指定节点的上一个节点信息。
		final Node<E> pred = succ.prev;
		// 新节点
		final Node<E> newNode = new Node<>(pred, e, succ);
		// 设置指定节点前一个节点就是新加入的节点
		succ.prev = newNode;
		// 如果指定节点的前一个节点为空的话，没有链表
		if (pred == null) {
			first = newNode;
		} else {// 指定节点前一个节点的下一个节点就是新加入的节点
			pred.next = newNode;
		}

		size++;
		modCount++;
	}

	/**
	 * 取消第一个节点的引用
	 * 
	 * @param f
	 * @return
	 */
	private E unLinkFirst(Node<E> f) {
		final E element = f.item;
		final Node<E> next = f.next;
		f.item = null;
		f.next = null;
		// 更换第一个节点信息
		first = next;
		// 第一个节点的下一个节点为null，就说明只有一个元素了
		if (next == null) {
			last = null;
			// 设置前一个节点也为空，因为第一个节点是没有前一个节点的指针引用的
		} else {
			next.prev = null;
		}
		size--;
		modCount++;
		return element;
	}

	/**
	 * 取消最后一个节点的引用
	 * 
	 * @param l
	 * @return
	 */
	private E unLinkLast(Node<E> l) {
		final E element = l.item;
		final Node<E> pred = l.prev;
		l.item = null;
		l.prev = null;

		last = pred;
		if (last == null) {
			first = null;
		} else {
			pred.next = null;
		}

		size--;
		modCount++;
		return element;

	}

	/**
	 * 取消指定节点的引用
	 * 
	 * @param x
	 * @return
	 */
	E unLink(Node<E> x) {
		final E element = x.item;
		final Node<E> next = x.next;
		final Node<E> prod = x.prev;

		// 如果是第一个
		if (prod == null) {
			first = next;
			// 不是第一个，设置该节点的下一个节点为该节点的前指针的下一个节点的值
		} else {
			prod.next = next;
			x.prev = null;
		}

		// 如果是最后一个
		if (next == null) {
			last = prod;
			// 不是最后一个，设置该节点的下一个节点的前指针，指向该节点的前一个节点的指针
		} else {
			next.prev = prod;
			x.next = null;
		}

		x.item = null;
		size--;
		modCount++;
		return element;
	}

	/**
	 * 取得第一个元素
	 * 
	 * @return 第一个元素
	 */
	public E getFirst() {
		final Node<E> f = first;
		if (f == null)
			throw new NoSuchElementException();
		return f.item;
	}

	/**
	 * 取得最后一个元素
	 * 
	 * @return 最后一个元素
	 */
	public E getLast() {
		final Node<E> l = last;
		if (last == null)
			throw new NoSuchElementException();
		return l.item;
	}

	/**
	 * 删除第一个元素
	 * 
	 * @return 第一个被删除的元素
	 */
	public E removeFirst() {
		final Node<E> f = first;
		if (f == null)
			throw new NoSuchElementException();
		return unLinkFirst(f);
	}

	/**
	 * 删除最后一个元素
	 * 
	 * @return 最后一个被删除的元素
	 */
	public E removeLast() {
		final Node<E> l = last;
		if (l == null)
			throw new NoSuchElementException();
		return unLinkLast(l);
	}

	/**
	 * 增加一个元素到list的第一个位置
	 * 
	 * @param e
	 */
	public void addFirst(E e) {
		linkFirst(e);
	}

	/**
	 * 增加一个元素到list的结尾
	 * 
	 * @param e
	 */
	public void addLast(E e) {
		linkLast(e);
	}

	/**
	 * 在指定元素上加上元素
	 * 
	 * @param index
	 * @param element
	 */
	public void add(int index, E element) {
		checkIndex(index);
		if (index == size) {
			linkLast(element);
		} else {
			// 在哪个节点前加入元素
			linkBefore(element, node(index));
		}
	}

	/**
	 * 根据index获取，节点信息
	 * 
	 * @param index
	 * @return
	 */
	Node<E> node(int index) {
		// 如果是在大小一半之前，正序查找，否则倒序查找，提高效率
		if (index < (size >> 1)) {
			Node<E> f = first;
			for (int i = 0; i < index; i++) {
				f = f.next;
			}
			return f;
		} else {
			Node<E> l = last;
			for (int i = size - 1; i > index; i--) {
				l = l.prev;
			}
			return l;
		}
	}

	/**
	 * 校验索引是否符合信息
	 * 
	 * @param index
	 */
	private void checkIndex(int index) {
		if (!isElementIndex(index)) {
			throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
		}
	}

	/**
	 * 越界的错误信息。
	 * 
	 * @param index
	 * @return
	 */
	private String outOfBoundsMsg(int index) {
		return "Index: " + index + ", Size: " + size;
	}

	/**
	 * 检测索引是否溢出
	 * 
	 * @param index
	 * @return
	 */
	private boolean isElementIndex(int index) {
		return index >= 0 && index < size;
	}

	public static void main(String[] args) {
		LinkedList1 linkedList1 = new LinkedList1();
		linkedList1.addFirst('a');
		linkedList1.addFirst('b');
		System.out.println(linkedList1.getFirst());
	}
}